/**
 *    Copyright (C) 2008  Victor Smirnov <aist11@gmail.com>
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License along
 *    with this program; if not, write to the Free Software Foundation, Inc.,
 *    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 *    See LICENSE.exceptions in the root folder of this project for possible
 *    exceptions
 *
 */

#ifndef __MAP_TEST_BASE_HPP__
#define __MAP_TEST_BASE_HPP__

#include <cppunit/extensions/HelperMacros.h>
#include <cubefs/core/map.hpp>


namespace cubefs    {
namespace core      {
namespace tests     {
namespace map_ns    {

using namespace cubefs::core::map;
using namespace cubefs::core::btree;

template <typename MapType = KVMap<1, BigInt, Wrapper<BigInt>, SimplePageManager> >
class TestBase : public CPPUNIT_NS::TestFixture
{
protected:
    
    typedef SimplePageManager             page_mgr;
    typedef page_mgr::Page              page_t;
    typedef page_mgr::Transaction             txn_t;
    typedef page_mgr::Page::ID        ID;

    typedef MapType map_t;

    
    typedef typename map_t::Iterator           Iterator;
    typedef typename map_t::NodeBase            NodeBase;

    typedef typename map_t::PageTypes            PageTypes;

    typedef typename map_t::NodeDispatcher       NodeDispatcher;
    typedef typename map_t::LeafDispatcher       LeafDispatcher;
    typedef typename map_t::RootDispatcher       RootDispatcher;
    typedef typename map_t::InternalNodeDispatcher InternalNodeDispatcher;

    page_mgr mgr;
    txn_t txn;

public:

    TestBase() {}

    void setUp() {
        txn = mgr.begin();
    }

    void tearDown() {
        mgr.commit(txn);
    }

    BigInt random(BigInt limit) {
        return ::random() % limit;
    }

    Int pow(Int val, Int count) {
        Int result = 1;
        for (int c = 0; c < count; c++) {
            result *= val;
        }
        return result;
    }

    const Iterator get_first(NodeBase *node) {
        while (!node->is_leaf()) {
            node = map_t::get_child(node, 0, &mgr, txn);
        }
        return Iterator(node, 0, &mgr, &txn);
    }

    const Iterator get_last(NodeBase *node) {
        while (!node->is_leaf()) {
            node = map_t::get_last_child(node, &mgr, txn);
        }

        Iterator i(node, get_children_count<typename map_t::NodeDispatcher>(node), &mgr, &txn);
        i.setEof(true);
        return i;
    }

    NodeBase* create_tree(Int levels, Int children, Int size)
    {
        return create_tree(levels, children, size, levels);
    }

    NodeBase* create_tree(Int levels, Int children, Int size, Int level0)
    {
        BigInt key = 0;
        NodeBase *node = create_node(levels + 1, true);

        __create_tree(node, levels, children, level0, key);

        return node;
    }

    NodeBase *create_node(Int level, bool root)
    {
        return PageTypes::create_node(&mgr, txn, level, root);
    }

    void __create_tree(NodeBase* parent, Int level, Int children, Int level0, BigInt &key)
    {
        Int children0 = (level > level0 ? 1 : children);
        parent->set_leaf(level == 0);

        if (level == 0) {
            for (Int c = 0; c < children0; c++)
            {
                for (Int d = 0; d < map_t::Indexes; d++)
                {
                    cubefs::core::btree::set_key<NodeDispatcher>(parent, d, c, key);
                }
                cubefs::core::btree::set_data<NodeDispatcher>(parent, c, &key);
                
                key++;
            }
        }
        else {
            for (Int c = 0; c < children0; c++)
            {
                NodeBase *node = create_node(level, false);
                __create_tree(node, level - 1, children, level0, key);

                BigInt *keys = get_max_keys<NodeDispatcher, BigInt>(node);

                cubefs::core::btree::set_keys<InternalNodeDispatcher>(parent, c, keys);
                cubefs::core::btree::set_data<InternalNodeDispatcher>(parent, c, &node->id());
            }
        }
    }

    BigInt get_key(NodeBase *node, Int key)
    {
        return cubefs::core::btree::get_max_key<NodeDispatcher, BigInt>(node, key);
    }

    BigInt get_key(NodeBase *node, Int key, Int idx)
    {
        return cubefs::core::btree::get_key<NodeDispatcher, BigInt>(node, key, idx);
    }

    NodeBase* get_node(ID &id)
    {
        return static_cast<NodeBase*>(mgr.get(txn, id));
    }

    void dump(NodeBase *node, int idx = 0) {
        dump_node(node, idx);
    }


    void dump_node(NodeBase *node, int idx = 0)
    {
        cubefs::core::btree::Dump<NodeDispatcher>(node, idx);
    }

    void dump_tree(NodeBase *node, int idx = 0)
    {
        dump_node(node, idx);
        for (Int c = 0; c < get_children_count<map_t::NodeDispatcher>(node); c++)
        {
            if (!node->is_leaf())
            {
                NodeBase *node1 = map_t::get_child(node, c, &mgr, txn);
                CPPUNIT_ASSERT(node1 != NULL);
                dump_tree(node1, idx);
            }
        }
    }

    void remove_tree(NodeBase *node)
    {
        if (!node->is_leaf())
        {
            for (Int c = 0; c < get_children_count<typename map_t::NodeDispatcher>(node); c++)
            {
                remove_tree(map_t::get_child(node, c, &mgr, txn));
            }
        }
        mgr.free(txn, node);
    }

    void check_node(NodeBase *node, BigInt key, Int parent_idx, BigInt &page_count, BigInt &key_count) {
        BigInt keys[map_t::Indexes];
        for (Int c = 0; c < map_t::Indexes; c++) {
            keys[c] = key;
        }


        check_node(node, keys, parent_idx, page_count, key_count);
    }

    void check_tree(NodeBase *node, BigInt key, BigInt key_count) {
        BigInt keys[map_t::Indexes];
        for (Int c = 0; c < map_t::Indexes; c++) {
            keys[c] = key;
        }
        check_tree(node, keys, key_count);
    }

    void check_tree(NodeBase *node, const BigInt* keys, BigInt key_count) {

        BigInt page_count1, key_count1;
        check_node(node, keys, 0, page_count1, key_count1);

        CPPUNIT_ASSERT_EQUAL(node->counters().page_count(), page_count1);

        CPPUNIT_ASSERT_EQUAL(key_count, key_count1);

        Iterator i = get_first(node);

        bool last = 0;
        BigInt last_key;
        do {
            NodeBase *current = i.page();
            BigInt key = cubefs::core::btree::get_key<LeafDispatcher, BigInt>(current, 0, i.key_idx());
            
            if (last) {
                CPPUNIT_ASSERT(key >= last_key);
                last = true;
            }
        }
        while (i.next_key());

    }

    void check_node(NodeBase *node, const BigInt* keys, Int parent_idx, BigInt &page_count, BigInt &key_count)
    {
        CPPUNIT_ASSERT_EQUAL((Int)parent_idx, (Int)node->parent_idx());

        const BigInt *max_keys = get_max_keys<NodeDispatcher, BigInt>(node);
        for (Int d = 0; d < map_t::Indexes; d++)
        {
            CPPUNIT_ASSERT_EQUAL(keys[d], max_keys[d]);
        }

        BigInt children_count = get_children_count<NodeDispatcher>(node);
        if (node->is_leaf()) {
            page_count = 1;
            key_count = node->counters().key_count();

            CPPUNIT_ASSERT_EQUAL((BigInt)1, node->counters().page_count());

            
            CPPUNIT_ASSERT_EQUAL(children_count, node->counters().key_count());

            for (Int c = 1; c < children_count; c++)
            {
                const BigInt* keys0 = get_keys<NodeDispatcher, BigInt>(node, c);
                const BigInt* keys1 = get_keys<NodeDispatcher, BigInt>(node, c - 1);
                for (Int d = 0; d < map_t::Indexes; d++)
                {
                    if (keys1[d] > keys0[d]) {
                        dump(node);
                    }
                    CPPUNIT_ASSERT(keys1[d] <= keys0[d]);
                }
            }
        }
        else {
            page_count = 0;
            key_count = 0;
            
            for (Int c = 0; c < children_count; c++)
            {
                const BigInt* keys0 = get_keys<NodeDispatcher, BigInt>(node, c);

                if (c > 0)
                {
                    const BigInt* keys1 = get_keys<NodeDispatcher, BigInt>(node, c - 1);
                    for (Int d = 0; d < map_t::Indexes; d++)
                    {
                        CPPUNIT_ASSERT(keys1[d] <= keys0[d]);
                    }
                }

                NodeBase *child = map_t::get_child(node, c, &mgr, txn);

                NodeBase *parent = map_t::get_parent(child, &mgr, txn);

                CPPUNIT_ASSERT_EQUAL(node, parent);

                BigInt page_count1;
                BigInt key_count1;
                check_node(child, keys0, c, page_count1, key_count1);

                page_count += page_count1;
                key_count  += key_count1;
            }
            
            //dump(node);
            page_count++;

            if (node->counters().page_count() != page_count) {
               // dump(node);
            }

            CPPUNIT_ASSERT_EQUAL(node->counters().page_count(), page_count);
            CPPUNIT_ASSERT_EQUAL(node->counters().key_count(),  key_count );
        }
    }
     
};

} //map_ns
} //tests
} //core
} //cubefs

#endif
